The present invention relates to digital circuits used to manipulate words of binary data, and in particular to a circuit for rotating the bits inside single or multiple data operands.
Data within a computer or other digital circuit is typically organized into one or more standard data sizes, referred to as data words. For example, a very common data word size contains 32 bits of binary data. The size of the data word affects precision and/or resolution of the information contained within the digital circuit, with larger data sizes allowing greater precision and/or resolution because they can represent more values. Larger data words, however, require larger digital circuits to manipulate the data, leading to greater cost and complexity. In addition to manipulating data of a maximum data size, many digital circuits also allow data of smaller, evenly divided sizes to be manipulated. For example, a digital circuit with a maximum data word size of 32 bits might also manipulate 8-bit or 16-bit data. A data operand that is half the size of the maximum data word is typically called a half-word. When the extra precision is not required, manipulating smaller data operands may provide advantages such as requiring less memory to store the data or allowing multiple data operands to be manipulated simultaneously by the same circuit.
Two operations that have proven to be useful when working with digital data are rotation and shifting. The bits of data within a data word are arranged in a fixed order, typically from most significant bit (MSB) in the leftmost position to least significant bit (LSB) in the rightmost position. The rotation operation takes a data word as an input operand and rearranges the order of the bits within that data word by moving bit values to the left or the right by a number of bit positions which may be fixed or may be specified by a second input operand. When rotating to the left, bit values which are moved past the MSB bit position are inserted into the right side bit positions which have been left vacant by the other bits being moved to the left. When rotating to the right, bits which are moved past the LSB bit position are inserted into the left side bit positions in the same manner. For example, consider a 32-bit data word:                0101 0001 0000 0000 0000 0000 1010 1110        
An instruction to rotate this data word left by four bits results in the new value:                0001 0000 0000 0000 0000 1010 1110 0101        
Since the values of the bits that are being rotated out the top or bottom of the data word are wrapped around and inserted at the other end of the data word, no bit values are lost.
The second operation, shifting, also takes a data word as an input operand and rearranges the order of the bits within that data word by moving bit values to the left or the right by a number of bit positions which may be fixed or may be specified by a second input operand. A shift operation, however, discards the bit values that are moved past the MSB or LSB bit positions. The bit positions that are left empty by the shift operation are filled with a fixed value, most commonly either with all 0s or all 1s. As an example, consider a 32-bit data word:                0101 0001 0000 0000 0000 0000 1010 1110        
An instruction to shift this word left by four bits while inserting 0s results in the new value:                0001 0000 0000 0000 0000 1010 1110 0000        
It is also common when shifting to the right to use the value of the MSB bit position to fill the bit positions that are left empty. For signed binary numbers, this has the property of ensuring that the number keeps the same sign.
Barrel shifters permit rotation or shifting of an n-bit word to the left or right by 0, 1, 2, . . . n−1 bits. When implementing with standard logic cells, barrel shifters are typically constructed out of multiple stages of multiplexers. In general, a multiplexer is essentially a selector that selects one of multiple inputs to be the output based on one or more control inputs. The two most prevalent types of multiplexers are 2:1 multiplexers that have two data inputs and one control input that selects the output and 4:1 multiplexers that have four data inputs and two control inputs that select the output. Each stage of the barrel shifter requires one multiplexer for each bit of the data operand to be rotated or shifted. Each multiplexer's inputs are connected to the input data word in a uniform pattern relative to the output bit that multiplexer produces. For example, for the pattern n, n−1, n−2, and n−3, the 4:1 multiplexer that produces output bit 31 would be connected to input bits 31, 30, 29, and 28. A stage of multiplexers with this pattern would allow a rotate left by 0, 1, 2, or 3 bits.
A barrel shifter for 32-bit data operands can be constructed using three stages of multiplexers. The first stage uses 4:1 multiplexers with the pattern n, n−1, n−2, and n−3 to rotate left by 0, 1, 2, or 3 bits. The second stage uses 4:1 multiplexers with the pattern n, n−4, n−8, and n−12 to rotate left by 0, 4, 8, or 12 bits. The third stage uses 2:1 multiplexers with the pattern n and n−16 to rotate left by 0 or 16 bits. To rotate a data operand left by 21 bits, the first stage would rotate left by one. Then the second stage would rotate left by four. Finally, the third stage would rotate left by sixteen. Since rotation is circular, rotates right may be handled by rotating left by 32 minus number of bits to rotate right. Insertion of ones or zeros as required for shifting operations can be handled in a fourth stages that follows the three stages of rotation performed by the multiplexers.
This 32-bit barrel shifter may be modified to process two 16-bit data operands simultaneously, providing high data throughput for 16-bit data without the increase in physical area that would be required for separate circuits for 16-bit data. Modifying this 32-bit barrel shifter to process two 16-bit data operands requires special handling where the bits being rotated cross the half-word boundary. Previous solutions used additional 2:1 multiplexers before the first and second multiplexer stages to select the correct input bits depending on whether 16 or 32-bit data was being rotated. For example, consider the inputs needed to generate output bit 17 from the first stage where the pattern is n, n−1, n−2, or n−3. For 32-bit data, the inputs are bits 17, 16, 15, and 14. For 16-bit data, the correct inputs are bits 17, 16, 31, and 30. In this approach, two additional 2:1 multiplexers are used to select between bits 15 and 31 and between bits 14 and 30 depending on the input data size. These additional multiplexers, however, increase the number of levels of logic required to calculate the result, decreasing the circuit's maximum speed performance, and increase the physical size of the circuit.